/*
 ** Trie.java
 ** Login : <speedblue@happycoders.org>
 ** Started on  Wed Nov  1 19:34:21 2006 Julien Lemoine
 ** $Id$
 **
 ** Copyright (C) 2006 Julien Lemoine
 ** This program is free software; you can redistribute it and/or modify
 ** it under the terms of the GNU General Public License as published by
 ** the Free Software Foundation; either version 2 of the License, or
 ** (at your option) any later version.
 **
 ** This program is distributed in the hope that it will be useful,
 ** but WITHOUT ANY WARRANTY; without even the implied warranty of
 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 ** GNU General Public License for more details.
 **
 ** You should have received a copy of the GNU General Public License
 ** along with this program; if not, write to the Free Software
 ** Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
 */

package org.speedblue.util;

/**
 * This class implement a trie in memory with the smallest memory
 * structure as possible. This string associate an integer to a string and
 * can be use very easilly with addEntry and getEntry method
 */
public class Trie {
    /// factory to create nodes
    private TrieNodeFactory factory;
    private int wordsNum;
    private int maxLength;
    private int minLength;
    
    /**
     * create the trie with a specific number of node at the
     * begining.
     * @param initialNbNodes
     */
    public Trie(int initialNbNodes) {
        factory = new TrieNodeFactory(initialNbNodes);
        factory.newNode(); // initial node
        wordsNum = 0;
        maxLength = 0;
        minLength = 0;
    }
    
    /**
     * add an String entry in trie. Value must be different than -1
     * (-1 is reserved when there is no match found)
     * @param str
     * @param value
     * @throws java.lang.Exception
     */
    public void addEntry(String str, int value) throws Exception {
        int currentNode = _addEntry(str);
        
        // Set the value on the last node
        if (currentNode >= 0 && getNodeValue(currentNode) != -1)
            throw new Exception("The word is already in trie");
        else {
            int len = str.length();
            if (wordsNum == 0) {
                wordsNum = 1;
                maxLength = len;
                minLength = len;
            } else {
                wordsNum++;
                if (len > maxLength)
                    maxLength = len;
                if (len < minLength)
                    minLength = len;
            }
        }
        _setNodeValue(currentNode, value);
    }
    
    /**
     * set an String entry in trie. Value must be different than -1
     * (-1 is reserved when there is no match found)
     * @param str
     * @param value
     * @throws java.lang.Exception
     */
    public void setEntry(String str, int value) throws Exception {
        int currentNode = _addEntry(str);
        
        // Set the value on the last node
        _setNodeValue(currentNode, value);
    }
    
    /**
     * get integer associated to a string, return -1 if entry is not found.
     * @param str 
     * @return integer value associated to an entry
     */
    public int getEntry(String str) {
        int currentNode = 0, strPos = 0;
        boolean	found = true;
        
        // Look for the part of the word which is in Trie
        while (found && strPos < str.length()) {
            found = false;
            currentNode = _lookingSubNode(currentNode, str.charAt(strPos));
            if (currentNode >= 0) {
                found = true;
                ++strPos;
            }
        }
        
        if (currentNode > 0 && strPos == str.length()) // The word is complet in the automaton
            return getNodeValue(currentNode);
        return -1;
    }
    
    /**
     * display the whole content of trie
     */
    public void display() {
        _display(0, (char)0, -2);
    }
    
    /**
     * accessor to iterator over the trie. the initial node is 0.
     * return -1 when there is no subnode
     * @param node - node id of parent node 
     * @return node id of first subnode
     */
    public int getFirstSubNode(int node) {
        return factory.getFirstSubNode(node);
    }
    
    /**
     * accessor to iterator over the trie. the initial node is 0.
     * @param node
     * @return label (character)
     */
    public char getFirstSubNodeLabel(int node) {
        return factory.getFirstSubNodeLabel(node);
    }
    
    /**
     * accessor to iterator over the trie. the initial node is 0.
     * return -1 when there is no sub node
     * @param node - node id
     * @return node id of brother node
     */
    public int getBrother(int node) {
        return factory.getBrother(node);
    }
    
    /**
     * accessor to iterator over the trie. the initial node is 0.
     * @param node
     * @return label (character)
     */
    public char getBrotherLabel(int node) {
        return factory.getBrotherLabel(node);
    }
    
    /**
     * accessor to iterator over the trie. the initial node is 0
     */
    public int getNodeValue(int node) {
        return factory.getValue(node);
    }
    
    /**
     * 
     * @return numbers of words in the trie
     */
    public int size() {
        return wordsNum;
    }

    /**
     * @return length of the longest word in the trie
     */
    public int getMaxLength() {
        return maxLength;
    }

    /**
     * @return length of the shortest word in the trie
     */
    public int getMinLength() {
        return minLength;
    }
    
    /**
     * display content of a node and his sub nodes
     */
    protected void _display(int node, char label, int offset) {
        int firstSubNode = factory.getFirstSubNode(node);
        char firstSubNodeLabel = factory.getFirstSubNodeLabel(node);
        int brother = factory.getBrother(node);
        char brotherLabel = factory.getBrotherLabel(node);
        
        if (label != 0) {
            for (int i = 0; i < offset; ++i)
                System.out.print(" ");
            System.out.println("label[" + label + "]");
        }
        if (firstSubNode >= 0)
            _display(firstSubNode, firstSubNodeLabel, offset + 2);
        if (brother >= 0)
            _display(brother, brotherLabel, offset);
    }
    
    /**
     * add an element in sub nodes
     */
    protected void _addSubNode(int node, char chr, int newNode) {
        int firstSubNode = factory.getFirstSubNode(node);
        char firstSubNodeLabel = factory.getFirstSubNodeLabel(node);
        
        if (firstSubNode < 0 || firstSubNodeLabel > chr) {
            factory.setBrother(newNode, firstSubNode, firstSubNodeLabel);
            factory.setFirstSubNode(node, newNode, chr);
        } else
            _addBrother(firstSubNode, chr, newNode);
    }
    
    /**
     * add an element in list of brother
     */
    protected void _addBrother(int node, char chr, int newNode) {
        int brother = factory.getBrother(node);
        char brotherLabel = factory.getBrotherLabel(node);
        
        if (brother < 0 || brotherLabel > chr) {
            factory.setBrother(newNode, brother, brotherLabel);
            factory.setBrother(node, newNode, chr);
        } else
            _addBrother(brother, chr, newNode);
    }
    
    /**
     * Looking for a sub node of node accessible with chr
     */
    protected int _lookingSubNode(int node, char chr) {
        int firstSubNode = factory.getFirstSubNode(node);
        char firstSubNodeLabel = factory.getFirstSubNodeLabel(node);
        
        if (firstSubNode >= 0 && firstSubNodeLabel <= chr) {
            if (firstSubNodeLabel == chr)
                return firstSubNode;
            return _lookingBrother(firstSubNode, chr);
        }
        return -1;
    }
    
    /**
     * Looking for a node accessible with chr in list of brother
     * of node
     */
    protected int _lookingBrother(int node, char chr) {
        int brother = factory.getBrother(node);
        char brotherLabel = factory.getBrotherLabel(node);
        
        if (brother >= 0 && brotherLabel <= chr) {
            if (brotherLabel == chr)
                return brother;
            return _lookingBrother(brother, chr);
        }
        return -1;
    }
    
    /// set value of node
    protected void _setNodeValue(int node, int value) {
        factory.setValue(node, value);
    }
    
    /**
     * add an String entry in trie.
     */
    protected int _addEntry(String str) throws Exception {
        int currentNode = 0, previousNode = 0, strPos = 0;
        boolean	found = true;
        
        // Look for the part of the word which is in Trie
        while (found && strPos < str.length()) {
            found = false;
            previousNode = currentNode;
            currentNode = _lookingSubNode(currentNode, str.charAt(strPos));
            if (currentNode >= 0) {
                found = true;
                ++strPos;
            }
        }
        // Add part of the word which is not in Trie
        if (currentNode < 0 || strPos != str.length()) {
            currentNode = previousNode;
            while (strPos < str.length()) {
                int newNode = factory.newNode();
                _addSubNode(currentNode, str.charAt(strPos), newNode);
                currentNode = newNode;
                ++strPos;
            }
        }
        if (currentNode < 0)
            throw new Exception("Buggy Trie");
        return currentNode;
    }
    
}
